//
//  714. 买卖股票的最佳时机含手续费.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/25.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution714 {
    // 持有股票dp[i][0]
    // 不持有股票dp[i][1]
    func maxProfit(_ prices: [Int], _ fee: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
        dp[0][0] = -prices[0]
        for i in 1..<prices.count {
            // 持有股票：1.本身持有;2. 购买而来
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            // 不持有股票: 1. 本身不持有 2. 卖出而来
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)
        }
        return dp[prices.count - 1][1]
    }
    static func test() {
        let array = [1, 3, 2, 8, 4, 9]
        let restu = Solution714().maxProfit(array, 2)
        print(restu)
    }
}
